import jdk.nashorn.internal.ir.WhileNode;

import java.util.Stack;

/**
 * @author yexiebao
 * @date 2025/5/16
 */

public class RemoveNthFromEnd {
    // 方法一：
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return null;
        }
        int num = 0;
        ListNode curr = head;
        while( curr!=null){
            num++;
            curr =  curr.next;
        }
        if(n<=0 || num<n ){
            return null;
        }
        if(num == n){
            head = head.next;

        }else{
            int preNum = 0;
            preNum = num - n -1;
            ListNode preNode = head;
            while(preNum>0){
                preNode = preNode.next;
                preNum--;
            }
            preNode.next = preNode.next.next;
        }
        return head;
    }

    //方法二：双指针
    public static ListNode removeNthFromEndUsingTwoPointers(ListNode head, int n) {
        if(head ==null || n <= 0){
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode tail=dummy, pre = dummy;
        for(int i=0;i<n;i++){
            tail = tail.next;
        }
        while(tail.next != null){
            tail = tail.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }
    //方法三：栈
    public static ListNode removeNthFromEndUsingStack(ListNode head, int n) {
        if(head == null){
            return null;
        }
        int num = 0;
        ListNode curr = head;
        while( curr!=null){
            num++;
            curr =  curr.next;
        }
        if(n<=0 || num<n ){
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        curr = head;
        while(curr!=null){
            stack.push(curr);
            curr =  curr.next;
        }
        ListNode newHead = new ListNode();
        Stack<ListNode> stack2 = new Stack<>();
        curr = newHead;
        num = 1;
        while(!stack.empty()){
            curr.next = stack.pop();
            if(num!=n){
                stack2.push(curr.next);
            }
            curr = curr.next;
            num++;
        }
        curr.next = null;
        curr = newHead;
        while(!stack2.empty()){
            curr.next = stack2.pop();
            curr = curr.next;
        }
        curr.next = null;
        head = newHead.next;
        return head;
    }
    public static ListNode removeNthFromEndUsingStack2(ListNode head, int n) {
        if(head == null ||  n<=0){
            return head;
        }
        ListNode newHead = new ListNode();
        newHead.next = head;
        Stack<ListNode>stack = new Stack<>();
        ListNode curr = newHead;
        while(curr!=null){
            stack.push(curr);
            curr = curr.next;
        }
        for(int i=0;i<n;i++){
            if(!stack.isEmpty()){
                stack.pop();
            }else{
                return head;
            }
        }
        ListNode preNode = stack.pop();
        preNode.next = preNode.next.next;
        return newHead.next;

    }
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(4);
//        ListNode node5 = new ListNode(5);
        ListNode head = node1;
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
        node1.next = null;
        ListNode newHead = removeNthFromEndUsingTwoPointers(head,1);
        while(newHead!=null){
            System.out.println(newHead.val);
            newHead = newHead.next;
        }
    }
}